In networking systems, routers and/or switches typically move packets of information from one of a number of input ports to one or more output ports. A lookup function, which can be implemented as a hardware “search engine” or the like, can include a content addressable memory (CAM), but this approach may be relatively expensive. Another approach is to use a standard memory, such as static random-access memory (SRAM), commonly accessed using “hashing” to essentially provide a “many-to-one” function. Such an approach can allow for a smaller memory size so that the overall system cost can be reduced.
Referring now to FIG. 1, a block diagram of a conventional search engine using hashing is shown and indicated by the general reference character 100. Hash Function 102-0 can receive Key 0 and provide hash function output H0 to Memory Bank 104-0. Similarly, Hash Function 102-1 can receive Key 1 and provide hash function output H1 to Memory Bank 104-1, and so on through Hash Function 102-N receiving Key N and providing hash function output HN to Memory Bank 104-N. In this fashion, each hash function maps to a designated memory bank or section. So, none of the entries in Memory Bank 104-0 can use a function or rule other than H0. Because different applications may require different and/or multiple rules, several of the memory banks may be under utilized in this conventional approach. Further, features commonly available in CAM-based search engines, such as key concatenation, incoming key masking, local masking, and other flexible system options are typically not provided in such conventional SRAM-based search engines.
Consequently, what is needed is a search engine solution that does not include a CAM structure, but still provides at a relatively low cost, features such as key concatenation, masking of incoming keys, local masking for each stored key, and flexibility in rule sharing through the use of different hash function outputs.